package labuladong;

public class BinarySearch {


    //  CKG TODO 2023/6/5: 有一点不太理解呢　
    int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }


    int left_search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        //  CKG TODO 2023/6/5: 有一点不太理解呢　

        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }


    int right_search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        //  CKG TODO 2023/6/5: 有一点不太理解呢　
        if (right< 0 || nums[right] != target) {
            return -1;
        }
        return right;
    }


    int shipWithThinDays(int[]  weights,int D){
        int left=getMax(weights);
        int right=getSum(weights);
        while (left<=right){
            int mid=left+(right-left)/2;
            if (isCanFinish(weights,mid,D)){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        return  left;
    }

    boolean isCanFinish(int[] weights,int speed,int D){
        int length = weights.length;
        int n=0;
        int sum=0;
        int time=0;
        while (n<length){
            sum+=weights[n++];
            if (sum>speed){
                time++;
                sum=weights[n-1];
            }
        }
        if (sum<=speed){
            time++;
        }
        return  time<=D?true:false;
    }



    int getMax(int[] weights){
        int max=0;
        for (int a : weights) {
            max=Math.max(a,max);
        }
        return  max;
    }


    int getSum(int[] weights){
        int sum=0;
        for (int a :weights) {
            sum+=a;
        }
        return  sum;
    }

    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        int[] weights={1,2,3,4,5,6,7,8,9,10};
        System.out.println(binarySearch.shipWithThinDays(weights, 5));
    }



}
